/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 石方旭
 * Date: 2022-04-03
 * Time: 17:29
 */

// Java program to rotate a matrix
import java.lang.*;
import java.util.*;
import java.io.*;


// This code is contributed by Sahil_Bansall

public class TestDemo {


    static int i, j;

    /* This function partitions a[] in three parts
       a) a[l..i] contains all elements smaller than pivot
       b) a[i+1..j-1] contains all occurrences of pivot
       c) a[j..r] contains all elements greater than pivot */
    static void partition(int a[], int l, int r) {

        i = l - 1;
        j = r;
        int p = l - 1, q = r;
        int v = a[r];

        while (true) {

            // From left, find the first element greater than
            // or equal to v. This loop will definitely
            // terminate as v is last element
            while (a[++i] < v)
                ;

            // From right, find the first element smaller than
            // or equal to v
            while (v < a[--j])
                if (j == l)
                    break;

            // If i and j cross, then we are done
            if (i >= j)
                break;

            // Swap, so that smaller goes on left greater goes
            // on right
            int temp = a[i];
            a[i] = a[j];
            a[j] = temp;

            // Move all same left occurrence of pivot to
            // beginning of array and keep count using p
            if (a[i] == v) {
                p++;
                temp = a[i];
                a[i] = a[p];
                a[p] = temp;

            }

            // Move all same right occurrence of pivot to end of
            // array and keep count using q
            if (a[j] == v) {
                q--;
                temp = a[q];
                a[q] = a[j];
                a[j] = temp;
            }
        }

        // Move pivot element to its correct index
        int temp = a[i];
        a[i] = a[r];
        a[r] = temp;

        // Move all left same occurrences from beginning
        // to adjacent to arr[i]
        j = i - 1;
        for (int k = l; k < p; k++, j--) {
            temp = a[k];
            a[k] = a[j];
            a[j] = temp;
        }

        // Move all right same occurrences from end
        // to adjacent to arr[i]
        i = i + 1;
        for (int k = r - 1; k > q; k--, i++) {
            temp = a[i];
            a[i] = a[k];
            a[k] = temp;
        }
    }

    // 3-way partition based quick sort
    static void quicksort(int a[], int l, int r) {
        if (r <= l)
            return;

        i = 0;
        j = 0;

        // Note that i and j are passed as reference
        partition(a, l, r);

        // Recur
        quicksort(a, l, j);
        quicksort(a, i, r);
    }

    // A utility function to print an array
    static void printarr(int a[], int n) {
        for (int i = 0; i < n; ++i)
            System.out.printf("%d  ", a[i]);
        System.out.printf("\n");
    }

    // Driver code
    public static void main(String[] args) {
        int a[] = {4, 9, 4, 4, 1, 9, 4, 4, 9, 4, 4, 1, 4};
        int size = a.length;

        // Function Call
        printarr(a, size);
        quicksort(a, 0, size - 1);
        printarr(a, size);
    }
}
//
//        // Function print matrix in spiral form
//        static void spiralPrint(int m, int n, int a[][])
//        {
//            int i, k = 0, l = 0;
//
//		/* k - starting row index
//		m - ending row index
//		l - starting column index
//		n - ending column index
//		i - iterator
//		*/
//            while (k < m && l < n) {
//                // Print the first row from the remaining rows
//                for (i = l; i < n; ++i) {
//                    System.out.print(a[k][i] + " ");
//                }
//                k++;
//
//                // Print the last column from the remaining
//                // columns
//                for (i = k; i < m; ++i) {
//                    System.out.print(a[i][n - 1] + " ");
//                }
//                n--;
//
//                // Print the last row from the remaining rows */
//                if (k < m) {
//                    for (i = n - 1; i >= l; --i) {
//                        System.out.print(a[m - 1][i] + " ");
//                    }
//                    m--;
//                }
//
//                // Print the first column from the remaining
//                // columns */
//                if (l < n) {
//                    for (i = m - 1; i >= k; --i) {
//                        System.out.print(a[i][l] + " ");
//                    }
//                    l++;
//                }
//            }
//        }
//
//        // Driver Code
//        public static void main(String[] args)
//        {
//            int R = 3;
//            int C = 6;
//            int a[][] = { { 1, 2, 3, 4, 5, 6 },
//                    { 7, 8, 9, 10, 11, 12 },
//                    { 13, 14, 15, 16, 17, 18 } };
//
//            // Function Call
//            spiralPrint(R, C, a);
//        }

// Contributed by Pramod Kumar

//    static int R = 4;
//    static int C = 4;
//
//    // A function to rotate a matrix
//    // mat[][] of size R x C.
//    // Initially, m = R and n = C
//    static void rotateMatrix(int m, int n, int mat[][])
//    {
//        int row = 0, col = 0;
//        int prev, curr;
//
//		/*
//		row - Starting row index
//		m - ending row index
//		col - starting column index
//		n - ending column index
//		i - iterator
//		*/
//        while (row < m && col < n)
//        {
//
//            if (row + 1 == m || col + 1 == n)
//                break;
//
//            // Store the first element of next
//            // row, this element will replace
//            // first element of current row
//            prev = mat[row + 1][col];
//
//            // Move elements of first row
//            // from the remaining rows
//            for (int i = col; i < n; i++)
//            {
//                curr = mat[row][i];
//                mat[row][i] = prev;
//                prev = curr;
//            }
//            row++;
//
//            // Move elements of last column
//            // from the remaining columns
//            for (int i = row; i < m; i++)
//            {
//                curr = mat[i][n-1];
//                mat[i][n-1] = prev;
//                prev = curr;
//            }
//            n--;
//
//            // Move elements of last row
//            // from the remaining rows
//            if (row < m)
//            {
//                for (int i = n-1; i >= col; i--)
//                {
//                    curr = mat[m-1][i];
//                    mat[m-1][i] = prev;
//                    prev = curr;
//                }
//            }
//            m--;
//
//            // Move elements of first column
//            // from the remaining rows
//            if (col < n)
//            {
//                for (int i = m-1; i >= row; i--)
//                {
//                    curr = mat[i][col];
//                    mat[i][col] = prev;
//                    prev = curr;
//                }
//            }
//            col++;
//        }
//
//        // Print rotated matrix
//        for (int i = 0; i < R; i++)
//        {
//            for (int j = 0; j < C; j++)
//                System.out.print( mat[i][j] + " ");
//            System.out.print("\n");
//        }
//    }
//
//    /* Driver program to test above functions */
//    public static void main(String[] args)
//    {
//        // Test Case 1
//        int a[][] = { {1, 2, 3, 4},
//                {5, 6, 7, 8},
//                {9, 10, 11, 12},
//                {13, 14, 15, 16} };
//
//        // Test Case 2
//	/* int a[][] = new int {{1, 2, 3},
//							{4, 5, 6},
//							{7, 8, 9}
//						};*/
//        rotateMatrix(R, C, a);
//
//    }
